{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Circle of Chained Words（单词接龙环）\n",
    "\n",
    "[@mjd507][1] ｜ [WeChat Channel（微信公众号）][2]\n",
    "\n",
    "[1]: https://github.com/mjd507\n",
    "[2]: https://mp.weixin.qq.com/s/aNnkv3aG3YhJCHA_f2CtWA\n",
    "\n",
    "![Logo](images/Day72-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two words can be *chained* if the last character of the first word is the same as the first character of the second word.\n",
    "\n",
    "Given a list of words, determine if there is a way to *chain* all the words in a circle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当首个单词的词尾字符和第2个单词的词首字符相同时，2个单词可以被*接龙*。\n",
    "\n",
    "给定一组单词，判断它们能否接成一个环。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Starting Point（初始代码）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chainedWords(words: list) -> bool:\n",
    "    def DFS(graph: defaultdict, visited: list, current_word: str,\n",
    "            start_word: str, words_count: int) -> bool:\n",
    "        ''' Define a recursive local function '''\n",
    "        # Get the last character of the current word.\n",
    "        last_char = current_word[-1]\n",
    "        # If there lefts only 1 word, ...\n",
    "        if words_count == 1:\n",
    "            # check if they can be attached into a circle.\n",
    "            return (start_word[0] == last_char)\n",
    "        # Set the current word as visited, and ignore it in the following search.\n",
    "        visited[current_word] = True\n",
    "        # Find out all words that can be attached to the chain.\n",
    "        for node in (graph[last_char] or []):\n",
    "            # If it hasn't been visited, ...\n",
    "            if visited[node] is False:\n",
    "                # Keep searching recursively.\n",
    "                return DFS(graph, visited, node, start_word, words_count - 1)\n",
    "        # Otherwise, no words can be attached and no circle can be chained.\n",
    "        return False\n",
    "    \n",
    "    # Generate an empty dictionary.\n",
    "    graph = defaultdict(lambda: list())\n",
    "    # Traverse all words ...\n",
    "    for word in words:\n",
    "        # and map them with their starting letter.\n",
    "        graph[word[0]].append(word)\n",
    "    # Start searching recursively.\n",
    "    return DFS(graph, defaultdict(lambda: False), words[0], words[0], len(words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases（测试用例）\n",
    "\n",
    "```python\n",
    "Input: ['eggs', 'karat', 'apple', 'snack', 'tuna']\n",
    "Output: True\n",
    "```\n",
    "\n",
    "The words in the order of `['apple', 'eggs', 'snack', 'karat', 'tuna']` creates a circle of chained words.\n",
    "\n",
    "单词`['apple', 'eggs', 'snack', 'karat', 'tuna']`按顺序组成了一个单词接龙环。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chainedWords(['apple', 'eggs', 'snack', 'karat', 'tuna'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Afterword（后记）\n",
    "\n",
    "The above code was refactored from JavaScript version by [@mjd507][1]. Thanks!\n",
    "\n",
    "以上代码重构自[@mjd507][1]编写的JavaScript版本，谢谢！\n",
    "\n",
    "[1]: https://github.com/mjd507"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
